package com.algorithm.liyc.practice;

import com.algorithm.liyc.entity.ListNode;

/**
 * 链表相交
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
 *
 * @author Liyc
 * @date 2023/11/23 17:45
 **/

public class Solution12 {
    /**
     * ● 时间复杂度：O(n + m)
     * ● 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //求长度
        ListNode curA = headA;
        ListNode curB = headB;
        int countA = 0;
        int countB = 0;
        while (curA != null) {
            countA++;
            curA = curA.next;
        }
        while (curB != null) {
            countB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;

        //A作为最长的
        if (countA<countB) {
            int tmp = countA;
            countA = countB;
            countB = tmp;
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //长度差
        int gap = countA - countB;
        //把最长的移到同等的地方
        while (gap-- > 0) {
            curA = curA.next;
        }
        //对比
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
